/**
 * @param {number[]} nums
 * @return {number}
 * 时间复杂度O(n^2)
 */
var lengthOfLIS = function(nums) {
  const dp = new Array(nums.length).fill(1);
  for(let i = 0; i<nums.length; i++) {
    for(let j=0; j<i; j++) {
      // 找出nums[j]比nums[i]小的元素，找到一个就让最长子序列长度加1
      if(nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i],dp[j] + 1);
      }
    }
  }
  //找出最大子序列
  return Math.max(...dp);
};
var arr = [1,3,4,6,2,7,9];
console.log(lengthOfLIS(arr)) // 6

//进阶版--找出最长递增子序列并返回数组
var MathLIS = function(nums) {
  if (nums.length === 0) return [];
  
  const dp = new Array(nums.length).fill(1);
  // 记录前驱节点
  const prev = new Array(nums.length).fill(-1);
  // 计算dp数组和前驱节点
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        prev[i] = j; // 记录前驱节点
      }
    }
  }
  // dp [1,2,3,4,2,5,6] prev [-1,0,1,2,0,3,5]
  // 找出最大长度和其位置
  let maxLen = Math.max(...dp);
  let cur = dp.indexOf(maxLen); // 从第一个最大值开始回溯

  // 回溯构建LIS
  const lis = [];
  while (cur !== -1) {
    lis.unshift(nums[cur]); // 添加到开头保持顺序
    cur = prev[cur]; // 回溯到前驱节点
  }
  
  return lis;
};
var arr = [1,3,4,6,2,7,9];
console.log(MathLIS(arr))

